
function preTravle(root) {
    if (!root) return [];
    let ans = [];
    let stack = [root];
    while (stack.length > 0) {
        let node = stack.pop();
        ans.push(node);
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    return ans;
}

function inTravle(root) {
    if (!root) return [];
    let ans = [];
    let stack = [];
    let cur = root;
    while (stack.length > 0 || cur !== null) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.left;
        }
        let node = stack.pop();
        ans.push(node);
        cur = cur.right;
    }
    return ans;
}

function lasTravle(root) {
    if (!root) return [];
    let ans = [];
    let stack = [];
    let cur = root;
    let prev = null;
    while (stack.length > 0 || cur !== null) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.left;
        }
        let node = stack.pop();
        if (node.right === null || node.right === prev) {
            ans.push(node);
            prev = node;
            cur = null;
        } else {
            stack.push(node);
            cur = node.right;
        }
    }
    return ans;
}